#include <bits/stdc++.h>
using namespace std;

// 查找一个乱序数组的中位数
// 方法一：使用STL中的sort排序算法，中位数第n/2个数
// 方法二：桶排法
// 方法三：二分法
const int N = 1e5 + 10;
int main()
{
    // 二分法查找中位数
    int a[] = {37, 5, 16, 4, 2, 9, 18, 11, 12};
    // 遍历数组找出最大值和最小值，作为初始的指针
    int mmin = N, mmax = 0;
    int length = sizeof(a) / sizeof(int);
    for (int i = 0; i < length; i++)
    {
        mmin = min(mmin, a[i]);
        mmax = max(mmax, a[i]);
    }
    // 找中间值肯定在mmin和mmax之间
    int l = mmin, r = mmax;
    // 二分模板
    while (l < r)
    {
        int mid = l + (r - l) / 2;
        int ctn = 0;
        for (int i = 0; i < length; i++)
        {
            if (a[i] > mid)
                ctn++;
        }
        if (ctn > length / 2)
            l = mid + 1;
        else
            r = mid;
    }
    cout << r << endl;

    return 0;
}